'''
有向图的权值查找最短路径
狄克斯特拉算法（只能用正权边）
'''

used_node = []
if __name__ == "__main__":
    infinity = float("inf")
    graph = {
        # 有向图
        'start': {
            'a': 6,
            'b': 2,
        },
        'a': {
            'fin': 1,
        },
        'b': {
            'a': 3,
            'fin': 5,
        },
        'fin': {

        },
    }
    parents = {
        # 散列表
        'a': 'start',
        'b': 'start',
        'fin': None,
    }
    costs = {
        # 开销表
        'a': 6,
        'b': 2,
        'fin': infinity,
    }


def find_low_node(costs):
    '''查找最小节点并返回'''
    low_cost = float('inf')
    low_cost_node = None
    for node in costs:
        cost_num = costs[node]
        if cost_num < low_cost and node not in used_node:
            low_cost = cost_num
            low_cost_node = node
    return low_cost_node


node = find_low_node(costs)
while node is not None:
    cost = costs[node]
    neighbors = graph[node]
    for n in neighbors.keys():
        new_cost = cost + neighbors[n]
        if costs[n] > new_cost:
            costs[n] = new_cost
            parents[n] = node
    used_node.append(node)
    node = find_low_node(costs)
print(parents['fin'], parents[parents['fin']], parents[parents[parents['fin']]])
print(costs['fin'])
